#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
typedef struct BinaryTree {
	char data;
	struct BinaryTree* left;
	struct BinaryTree* right;
}BTNode;



BTNode* CreateTree()
{
	BTNode* root;
	char ch;
	scanf("%c", &ch);
	if (ch == '#')
		root = NULL;
	else {
		if (!(root = (BTNode*)malloc(sizeof(BTNode))))
			exit(1);
		root->data = ch;
		root->left = CreateTree();
		root->right = CreateTree();

	}
	return root;
}

void PreOrderTree(BTNode* root)
{
	if (root == NULL)
		return;
	printf("%c", root->data);
	PreOrderTree(root->left);
	PreOrderTree(root->right);
}

void InOrderTree(BTNode* root)
{
	if (root == NULL)
		return;
	
	InOrderTree(root->left);
	printf("%c", root->data);
	InOrderTree(root->right);
}

void PostOrderTree(BTNode* root)
{
	if (root == NULL)
		return;

	PostOrderTree(root->left);
	
	PostOrderTree(root->right);
	printf("%c", root->data);
}

void DestroyTree(BTNode* root)
{
	if (root == NULL)
		return;
	DestroyTree(root->left);
	DestroyTree(root->right);
	free(root);
	root = NULL;
}

int main()
{
	BTNode* root = CreateTree();
	PreOrderTree(root);
	printf("\n");
	InOrderTree(root);
	printf("\n");
	PostOrderTree(root);
	printf("\n");
	DestroyTree(root);
	return 0;

}